---
title: "棋盘问题"
created: 2025-11-28
tags:
  - 算法
---

# 棋盘问题

## 题目 [棋盘问题](https://www.acwing.com/problem/content/description/1116/)

![[image-2adb3ca9.png]]

## 思路分析

可以按直接按点枚举

每个点有选与不选两种情况

不选就直接往下一个走（x,y+1) 已放的棋子数cnt保持不变 当然如果走到某行的行末 要跳转到下一行的第一个

然后因为每行只能放一个

所以可以直接枚举行 而不需要行内每个位置都枚举

同样也是选与不选两种方案 不放就跑去下一行cur+1, cnt不变

放的话 得满足 该行的某列是棋盘 且该列没放过 cur+1,cnt+1

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=10;
bool row[N],col[N];
char g[N][N];
int n,k;
int res;

void dfs(int x,int y,int cnt){
	if(cnt>k)
		return;
	if(y==n)
		y=0,x++;
	if(x==n){
		if(cnt==k){
		    res++;
// 			for(int i=0;i<n;i++){
// 				puts(g[i]);
// 			}
// 			puts("");
		}
		return;
	}
    //不选
    dfs(x,y+1,cnt);
    //选——首先得是棋盘 其次该点所在行列都没放过
	if(g[x][y]=='#' && !row[x] && !col[y]){
	    row[x]=col[y]=true;
		g[x][y]='@';
		dfs(x,y+1,cnt+1);
	    g[x][y]='#';
        row[x]=col[y]=false;
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	while(cin>>n>>k,n!=-1,k!=-1){
		for(int i=0;i<n;i++)
			cin>>g[i];
		res=0;
		dfs(0,0,0);
		cout<<res<<endl;
	}
	return 0;
 }
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=10;

bool col[N];

char g[N][N];

int n,k;

int res;

void dfs(int cur,int cnt){

	if(cur==n){

	    if(cnt==k)

	        res++;

	    return;

	}

    //不选

    dfs(cur+1,cnt);

    //选——当前行某列为棋盘(#) 且该列没放过

    for(int i=0;i<n;i++){

        if(g[cur][i]=='#' && !col[i]){

    	    col[i]=true;

    		g[cur][i]='@';

    		dfs(cur+1,cnt+1);

    	    g[cur][i]='#';

            col[i]=false;

    	}

    }

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	while(cin>>n>>k,n!=-1,k!=-1){

		for(int i=0;i<n;i++)

			cin>>g[i];

		res=0;

		dfs(0,0);

		cout<<res<<endl;

	}

	return 0;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[整体状态 棋盘问题|整体状态 棋盘问题]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/DFS/简单图/4、方格分割|4、方格分割]]